﻿#define  _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<ctype.h>
//
//
////模拟实现atoi
////1.字符前面的空白字符吸收
////2.数字之前只能有一个正负号
////3.返回的是整型，不能超出整形的范围
////4.判断返回值的有效性，是非法返回的0，还是正常返回的0
////5.遇到字符就停止
//
//enum Legel
//{
//	illegel,//非法返回
//	legel//合法返回
//}valid=illegel;
//
//int my_atoi(char* str)
//{
//	assert(str);
//	long long ret = 0;//防止数字过大溢出
//	//正负号
//	int flag = 1;
//	//先吸收前面的空白字符
//	while (isspace(*str))
//	{
//		str++;
//	}
//	//判断正负
//	if (*str == '+' || *str == '-')
//	{
//		if (*str == '-')
//		{
//			flag = -1;
//		}
//		str++;
//	}
//	if (*str < '0' || *str>'9')
//	{
//		//第一个就不是数字，非法返回
//		return 0;
//	}
//	//读取数字
//	while ((*str >= '0') && (*str <= '9') && ( * str != '\0'))
//	{
//	//说明是合法返回的
//		valid = legel;
//		ret = ret * 10 + flag * (*str - '0');
//		if (ret > INT_MAX || ret < INT_MIN)//判断是否溢出
//		{
//			valid = illegel;
//			return 0;
//		}
//		str++;
//	}
//	return (int)ret;
//}
//
//int main()
//{
//	char str[] = "   +5651a4222";
//	//char str[]="+-4222";
//	//int ret = atoi(str);
//	//printf("%d\n", ret);
//	int ret = my_atoi(str);
//	if (valid == 1)
//	{
//		printf("合法返回:");
//	}
//	else
//	{
//		printf("非法返回:");
//	}
//	printf("%d\n", ret);
//	return 0;
//}

//leetcode 645 错误的集合
//
//int* findErrorNums(int* nums, int numsSize, int* returnSize) {
//    int arr[5];
//    int i = 0;
//    int wrong = 0;
//    int lose = 0;
//    for (i = 1; i <= numsSize; i++) {
//        arr[i] = 1;
//    }
//    for (i = 0; i < numsSize; i++) {
//        if (arr[nums[i]] == 1) {
//            arr[nums[i]] = 0;
//        }
//        else {
//            wrong = nums[i];
//        }
//    }
//    for (i = 1; i <= numsSize; i++) {
//        if (arr[i] == 1) {
//            lose = i;
//            break;
//        }
//    }
//    returnSize = (int*)malloc(8);
//    if (returnSize == NULL) {
//        exit(-1);
//    }
//    returnSize[0] = wrong;
//    returnSize[1] = lose;
//    return returnSize;
//}
//int
//main()
//{
//    //int arr[4] = { 1,2,2,3 };
//    int arr[] = { 1,1 };
//    int* ret=NULL;
//    ret = findErrorNums(arr, 2, ret);
//    int i = 0;
//    for (i = 0; i < 2; i++)
//    {
//        printf("%d ", ret[i]);
//    }
//    free(ret);
//    return 0;
//}


//给定一个长度为 n 的非降序数组和一个非负数整数 k ，
//要求统计 k 在数组中出现的次数

//
//int GetNumberOfK(int* nums, int numsLen, int k) {
//    // write code here
//    if (nums == NULL || numsLen == 0)
//    {
//        return 0;
//    }
//    int left = 0;
//    int right = numsLen - 1;
//    int mid = (left + right) / 2;
//    int num = 0;
//    while (left < right)
//    {
//        if (k > nums[mid])
//        {
//            left = mid + 1;
//            mid = (left + right) / 2;
//        }
//        else if (k < nums[mid])
//        {
//            right = mid - 1;
//            mid = (left + right) / 2;
//        }
//        else {
//            break;
//        }
//    }
//    if (k == nums[mid])
//    {
//        num = 1;
//    }
//    //nums[mid]==k
//    int i = 0;
//    for (i = 1; i < numsLen; i++)
//    {
//        if (nums[mid + i] == k && mid + i < numsLen)
//        {
//            num++;
//        }
//        else {
//            break;
//        }
//    }
//    for (i = 1; i < numsLen; i++)
//    {
//        if (nums[mid - i] == k && mid - 1 >= 0)
//        {
//            num++;
//        }
//        else {
//            break;
//        }
//    }
//    return num;
//}

//
//小明同学最近开发了一个网站，在用户注册账户的时候，需要设置账户的密码，为了加强账户的安全性，小明对密码强度有一定要求：
//
//1. 密码只能由大写字母，小写字母，数字构成；
//
//2. 密码不能以数字开头；
//
//3. 密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种；
//
//4. 密码长度至少为8
//
//现在小明受到了n个密码，他想请你写程序判断这些密码中哪些是合适的，哪些是不合法的。

//
//
//#include <stdio.h>
//#include<string.h>
//#include<ctype.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    char str[101];
//    while (scanf("%s", str) != EOF)
//    {
//        int len = strlen(str);
//        if (len < 8)//判断长度
//        {
//            printf("NO\n");
//            continue;
//        }
//        //判断第一个是不是字母  
//        if (isalpha(*str))
//        {
//            int flag = 1;//记录是否有非法字符
//            int flag1 = 0;//记录是否有数字
//            int flag2 = 0;//记录是否有小写字母
//            int flag3 = 0;//记录是否有大写字母
//            int i = 0;
//            for (i = 0; i < len; i++)
//            {
//                if (isdigit(*(str + i)))
//                {
//                    flag1 = 1;
//                }
//                else if (islower(*(str + i)))
//                {
//                    flag2 = 1;
//                }
//                else if (isupper(*(str + i)))
//                {
//                    flag3 = 1;
//                }
//                else {
//                    flag = 0;
//                    break;
//                }
//            }
//            if (flag == 0)
//            {
//                printf("NO\n");
//                continue;
//            }
//            else {
//                if ((flag1 + flag2 + flag3) >= 2)
//                {
//                    printf("YES\n");
//                }
//                else {
//                    printf("NO\n");
//                }
//            }
//
//        }
//
//        else {
//            printf("NO\n");
//            continue;
//        }
//
//    }
//
//    return 0;
//}

//整数转换。编写一个函数，
//确定需要改变几个位才能将整数A转成整数B。


//
//int convertInteger(int A, int B) {
//    int i=0;
//    int num=0;
//    for(i=0;i<32;i++)
//    {
//        if(((A>>i)&1)!=((B>>i)&1))
//        {
//            num++;
//        }
//    }
//
//    return num;
//}

//
//long int n = A ^ B;//防止溢出
//int num = 0;
//int c;
//while (c = n & (n - 1))//求n的二进制有几个1
//{
//    n = c;
//    num++;
//}
////循环次数比1的数量小1
//return num + 1;

//
// 
// 求一个数组中最大数是否是其他数的两倍，如果是，返回下标，否则返回-1
//
//int dominantIndex(int* nums, int numsSize) {
//    int ret = -1;
//    int max1 = 0;//最大数
//    int max2 = 0;//第二大数
//    int i = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        if (nums[i] > max1)
//        {
//            ret = i;
//            max1 = nums[i];
//            max2 = max1;
//        }
//        else
//        {
//            if (i > 0)
//            {
//                if (nums[i] > max2)
//                {
//                    max2 = nums[i];
//                }
//            }
//        }
//    }
//    if (max1 >= 2 * max2)
//    {
//        return ret;
//    }
//    else
//    {
//        return -1;
//    }
//}
//
//int main()
//{
//    int arr[] = { 3,6,1,0 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    int ret=dominantIndex(arr, sz);
//    printf("%d\n", ret);
//
//    return 0;
//}


//给定两个数组 nums1 和 nums2 ，返回 它们的 交集。
//输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

//int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size,int* returnSize) {
//    int i = 0;
//    int j = 0;
//    int n = 0;
//    int retsize = 0;//返回的元素个数
//    int* ret = (int*)calloc(nums1Size, 4);
//    if (ret == NULL)
//    {
//        exit(-1);
//    }
//    for (i = 0; i < nums1Size; i++)
//    {
//        for (j = 0; j < nums2Size; j++)
//        {
//            if (nums1[i] == nums2[j])
//            {
//                int flag = 1;
//                for (n = 0; n < retsize; n++)
//                {
//                    if (nums1[i] == ret[n])
//                    {
//                        flag = 0;
//                        break;
//                    }
//                }
//                if (flag == 1)
//                {
//                    ret[retsize] = nums1[i];
//                    retsize++;
//                    break;
//                }
//            }
//        }
//    }
//    ret = (int*)realloc(ret, retsize * 4);
//    if (ret == NULL)
//    {
//        exit(-1);
//    }
//    *returnSize = retsize;//返回元素个数
//    return ret;
//}
//
//int main()
//{
//    int arr1[5] = { 4,4,3,5,6 };
//    int arr2[4] = { 4,3,1,2 };
//    int Size = 0;
//    int* returnSize = &Size;
//    int* ret = intersection(arr1, 5, arr2, 4,returnSize);
//    int i = 0;
//    for (i = 0; i < Size; i++)
//    {
//        printf("%d ", ret[i]);
//    }
//    free(ret);
//    return 0;
//}


//Lily上课时使用字母数字图片教小朋友们学习英语单词，
//每次都需要把这些图片按照大小（ASCII码值从小到大）排列收好。
//请大家给Lily帮忙，通过代码解决。
//Lily使用的图片使用字符"A"到"Z"、"a"到"z"、"0"到"9"表示。
//数据范围：每组输入的字符串长度满足
//1≤n≤1000

//
//#include <stdio.h>
//#include<stdlib.h>
//#include<string.h>
//int cmp(const void* a, const void* b)
//{
//    return strcmp((char*)a, (char*)b);
//}
//int main() {
//    char str[1001];
//    scanf("%s", str);
//    qsort(str, strlen(str), 1, cmp);
//    printf("%s\n", str);
//
//    return 0;
//}

//
//给你一个整数数组 nums ，请计算数组的 中心下标 。
//
//数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
//
//如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
//
//如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 - 1 。

//int leftSum(int* begin, int* end)
//{
//    if (begin == end)
//        return 0;
//    int sum = 0;
//    while (begin < end)
//    {
//        sum += *begin;
//        begin++;
//    }
//    return sum;
//}
//int rightSum(int* begin, int* end)
//{
//    if (begin == end)
//        return 0;
//    int sum = 0;
//    int* cur = begin + 1;
//    while (cur <= end)
//    {
//        sum += *cur;
//        cur++;
//    }
//    return sum;
//}
//
//int pivotIndex(int* nums, int numsSize) {
//    int i = 0;
//    // int flag=0;
//    int ret = -1;
//    for (i = 0; i < numsSize; i++)
//    {
//        int leftsum = leftSum(nums, nums + i);
//        int rightsum = rightSum(nums + i, (nums + numsSize - 1));
//        if (leftsum == rightsum)
//        {
//            // flag=1;
//            ret = i;
//            break;
//        }
//    }
//    return ret;
//
//}
//
//int main()
//{
//    int arr[10] = { 2,1,3,5,9,7,1,2,6,5 };
//    int ret=pivotIndex(arr, 10);
//    printf("%d\n", ret);
//
//    return 0;
//}
//
// 
// 更快速的方法
//
//int pivotIndex(int* nums, int numsSize) {
//    int leftsum = 0;
//    int rightsum = 0;
//    int ret = -1;
//    int i = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        rightsum += nums[i];
//    }
//    for (i = 0; i < numsSize; i++)
//    {
//        if (i == 0)
//        {
//            rightsum -= nums[i];
//        }
//        else if (i == numsSize)
//        {
//            rightsum = 0;
//        }
//        else
//        {
//            leftsum += nums[i - 1];
//            rightsum -= nums[i];
//        }
//        if (leftsum == rightsum)
//        {
//            ret = i;
//            break;
//        }
//    }
//    return ret;
//}


//编写一个函数，计算字符串中含有的不同字符的个数。
// 字符在 ASCII 码范围内(0~127 ，包括 0 和 127)，换行表示结束符，不算在字符里
// 000000000000000000000000000000000000000000000000000000不在范围内的不作统计。多个相同的字符只计算一次
//例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
//
//数据范围：1≤n≤500

//#include <stdio.h>
//#include<stdlib.h>
//int main() {
//    char str[501];
//    scanf("%s", str);
//    int* arr = (int*)calloc(127, 4);
//    int i = 0;
//    while (str[i] >= 0 && str[i] <= 127
//        && i < 500 && str[i])
//    {
//        arr[str[i]] = 1;
//        i++;
//    }
//    int sum = 0;
//    for (i = 0; i < 127; i++)
//    {
//        sum += arr[i];
//    }
//    printf("%d\n", sum);
//    return 0;
//}


//给定一个大小为 n 的数组 nums ，返回其中的多数元素。
//多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。


//int majorityElement(int* nums, int numsSize) {
//    int* arr = (int*)calloc(numsSize + 1, 4);
//    int i = 0;
//    int ret = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        arr[nums[i]] ++;//这是错误的，因为数组元素的值可能大于元素个数
//    }
//    for (i = 1; i < numsSize + 1; i++)
//    {
//        if(arr[i]>=numsSize/2)
//        {
//            ret = i;
//            break;
//        }
//    }
//    free(arr);
//    return ret;
//}


int main()
{
    int arr[6] = { 1,2,2,2,2,4 };
    int ret=majorityElement(arr, 6);
    printf("%d\n", ret);

    return 0;
}